//题目:
// 给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。
// 当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。

// 示例 1：
// 输入：s = "abcbdd"
// 输出：true
// 解释："abcbdd" = "a" + "bcb" + "dd"，三个子字符串都是回文的。

// 示例 2：
// 输入：s = "bcbddxy"
// 输出：false
// 解释：s 没办法被分割成 3 个回文子字符串。
#include<iostream>
#include<vector>

using namespace std;
//代码
class Solution 
{
public:
    bool dfs(const vector<vector<int>>& dp,int x,int y,int count)
    {
        if(count==3)
        {
            if(y==dp.size()-1) return true;
            else return false;
        }

        for(int i=y+1;i<dp.size();i++)
            if(dp[y+1][i]!=0 && dfs(dp,y+1,i,count+1)==true)
                return true;
        
        return false;
    }
    bool checkPartitioning(string s) 
    {
        int n=s.size();
        //一.先用一个dp表存放s中的所有回文子串
        //1.创建dp表————dp[i][j]表示:以s[i]为起始，以s[j]为终点，的字符串是否为回文字符串
        vector<vector<int>> dp(n,vector<int>(n));
        //2.初始化————无
        //3.填表————从右向左填
        for(int i=n-1;i>=0;i--)
        {
            for(int j=i;j<n;j++)
                if(s[i]==s[j] && (i==j || i+1==j || dp[i+1][j-1]!=0))
                    dp[i][j]=1;
        }
        //二.判断dp是否存在能够将s分割成三个回文子串————递归————超时
        // for(int i=0;i<n;i++)
        //     if(dp[0][i]!=0 && dfs(dp,0,i,1)==true)
        //         return true;

        //二.判断dp是否存在能够将s分割成三个回文子串————固定中间字符串
        for(int i=1;i<n-1;i++)//固定左边
        {
            for(int j=i;j<n-1;j++)//固定右边
                if(dp[0][i-1]!=0 && dp[i][j]!=0 && dp[j+1][n-1]!=0)
                    return true;
        }

        return false;
    }
};